package problems;

import dataStructures.Tuple;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: Vikas.Bhardwaj
 * Date: 5/24/12
 * Time: 5:47 PM
 * To change this template use File | Settings | File Templates.
 * A collection of common and hard interview problems solved using Dynamic Programming
 * in polynomial/ pseudo-polynomial time
 */
public class DynamicProgramming {

    public static int maxSumSubArray(int[] A) {
        int sum = 0;
        int maxSoFar = 0;
        int maxStart = 0, maxEnd = 0, currStart = 0, currEnd = 0;
        int n = A.length;
        for (int i1 = 0, aLength = A.length; i1 < aLength; i1++) {
            int i = A[i1];
            if (sum + i > sum) {
                sum += i;
                currEnd = i1;
            } else {
                if (maxSoFar < sum) {
                    maxSoFar = sum;
                    maxEnd = currEnd;
                    maxStart = currStart;
                }
                if (i > 0) {
                    currStart = i1;
                    currEnd = i1;
                    sum = i;
                } else {
                    sum = 0;
                    currStart = i1 + 1;
                    currEnd = i1;
                }
            }
        }
        if (maxSoFar < sum) {
            maxSoFar = sum;
            maxEnd = currEnd;
            maxStart = currStart;
        }
        System.out.println("The Max Sum found is " + maxSoFar + " found between " + maxStart + " and " + maxEnd);
        return maxSoFar;
    }

    public static void longestNonDecreasingSubSequence(int[] A) {

        int maxLengthSoFar = 0;
        int[] maxLengthTillCurrent = new int[A.length];
        int maxEndedAt = 0;
        int[] previousIndx = new int[A.length];


        for (int i = 0, aLength = A.length; i < aLength; i++) {
            previousIndx[i] = i;
            int x = A[i];
            int maxLengthForX = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (A[j] < x) {
                    int newMax = maxLengthTillCurrent[j] + 1;
                    if (newMax > maxLengthForX) {
                        maxLengthForX = newMax;
                        previousIndx[i] = j;
                    }
                }
            }
            maxLengthTillCurrent[i] = maxLengthForX;
            if (maxLengthForX > maxLengthSoFar) {
                maxLengthSoFar = maxLengthForX;
                maxEndedAt = i;
            }
        }

        System.out.println(" Longest NonDecreasing sub sequence for " + Arrays.toString(A) + " is of length " + maxLengthSoFar);

        int end = maxEndedAt;
        int next = -1;
        String output = "";
        while (true) {
            next = previousIndx[end];
            output = A[end] + " " + output;
            if (next == end) break;
            end = next;
        }

        System.out.println("The sequence is : " + output);
    }

    public static void longestCommonSubSequence() {

    }

    /**
     * There is a river that is n meters wide. At every meter from
     * the edge, there mayor may not be a stone. A frog needs to cross the river.
     * However the frog has the limitation that if it has just jumped x meters,
     * then its next jump must be between x-1 and x+1 meters, inclusive.
     * Assume the first jump can be of only 1 meter. Given the position of the
     * stones, how would you determine whether the frog can make it to the
     * other end or not? Analyze the runtime of your algorithm.
     *
     * @param stonePresence : false if no stone at that position, 1 if stone present
     */
    public static boolean frogProblem(boolean[] stonePresence) {
        boolean success = false;
        int[] jumpLength = new int[stonePresence.length];

        boolean[][] jumpNReach = new boolean[stonePresence.length][stonePresence.length];

        for (int i = 0, stonePositionsLength1 = stonePresence.length; i < stonePositionsLength1; i++) {
            boolean stonePresent = stonePresence[i];

            for (int jumpDist = i; jumpDist >= 0; jumpDist--) {
                if (stonePresent && (
                        jumpNReach[i - jumpDist][jumpDist] ||
                                jumpNReach[i - jumpDist][jumpDist - 1] ||
                                jumpNReach[i - jumpDist][jumpDist + 1])) {

                    jumpNReach[i][jumpDist] = true;
                }
            }
        }

        for (boolean ans : jumpNReach[stonePresence.length]) {
            if (ans) {
                success = true;
                break;
            }
        }

        return success;
    }


    /**
     * Knapsack Problem
     * Given a set of items, each with a weight and a value,
     * determine the number of each item to include in a collection so that the total weight
     * is less than or equal to a given limit and the total value is as large as possible.
     */
    public static int knapsackProblem(int C, int[] weight, int[] value) {
        int[] optimalValue = new int[C + 1];
        for (int i = 0; i <= C; i++) {
            optimalValue[i] = i > 0 ? optimalValue[i - 1] : 0;
            for (int j = 0; j < weight.length; j++) {
                int wt = weight[j];
                if (wt <= i) {
                    int prevCapacity = i - wt;
                    if (optimalValue[prevCapacity] + value[j] > optimalValue[i]) {
                        optimalValue[i] = optimalValue[prevCapacity] + value[j];
                    }
                }
            }
        }
        return optimalValue[C];

    }

    /**
     * We now consider an optimum planning problem in two dimensions. You
     * are given an L x lV rectangular piece of kite-paper, where L and Ware
     * positive integers and a list of n kinds of kites that can be made using
     * the paper. The i-th kite de?n? i ?[1 ?] requires an li x ?rectangle
     * of kite-paper; this kite sells for Pi' Assume li' ?i ? Pi are positive integers.
     * You have a machine that can cut rectangular pieces of kite-paper either
     * horizontally or vertically.
     * Problem 3.3: Design an algorithm that computes a pro?t maximizing
     * strategy for cutting the kite-paper. You can make as many instances of a
     * given kite as you want. There is no cost to cutting k?e-paper.
     * Looks similar to regular Knapsack problem
     * Multi dimensional Knapsack problem
     */
    public static void kitePaperProblem(int L, int W, Tuple<Integer>[] dimensions, int[] price) {

        int[][] optimalValue = new int[L + 1][W + 1];

        // fill the table initially with given values

        for (int i1 = 0, dimensionsLength = dimensions.length; i1 < dimensionsLength; i1++) {
            Tuple<Integer> dimension = dimensions[i1];
            if (dimension.getA() <= L && dimension.getB() <= W) {
                if (optimalValue[dimension.getA()][dimension.getB()] < price[i1]) {
                    optimalValue[dimension.getA()][dimension.getB()] = price[i1];
                }
            }
        }

        for (int i = 1; i <= L; i++) {
            for (int j = 1; j <= W; j++) {
                for (int k = i; k >= 0; k--) {
                    if (optimalValue[i][j] < optimalValue[i - k][j] + optimalValue[k][j]) {
                        optimalValue[i][j] = optimalValue[i - k][j] + optimalValue[k][j];
                    }
                }

                for (int k = j; k >= 0; k--) {
                    if (optimalValue[i][j] < optimalValue[i][j - k] + optimalValue[i][k]) {
                        optimalValue[i][j] = optimalValue[i][j - k] + optimalValue[i][k];
                    }
                }
            }
        }

        System.out.println(" MAX Value is " + optimalValue[L][W]);
        return;

    }

    /**
     *  Given a row of n houses and m colors, you need to color the houses such that
     *  no two adjacent houses have the same color and the cost is minimum.
     *  The cost of coloring house i with color j is given as input in color[i][j]
     */
    public static void colorHouses(int[][] color){
        // assuming that the we achieved the min (optimal) cost coloring
        // all houses till house i, we color house i+1
        // table houseColorCosts[i][j] indicates the minimum cost of coloring all
        //houses till house i optimally given that house i is colored with color j.

        if(color==null) return;
        int n = color.length;
        int m = color[0].length;
        int[][] houseColorCosts = new int[n][m];

        for(int i = 0 ;i < n ;i++){
            for(int j = 0;j<m;j++){
                if(i==0) houseColorCosts[i][j] = color[i][j];
                else{
                    int cost = color[i][j];
                    int minCost =0;
                    for(int k=0;k<m;k++){
                        if(j!=k && ( houseColorCosts[i][k]+cost < minCost) ){
                            minCost = houseColorCosts[i][k]+cost;
                        }
                    }
                }
            }
        }

        //finally get min of last house

        int minCost = houseColorCosts[n-1][0];

        for(int j=1; j < m;j++ ){
            if(minCost < houseColorCosts[n-1][j]) minCost = houseColorCosts[n-1][j];
        }
        System.out.println(" The min cost to color all houses is "+ minCost);
    }

    /**
     * Problem 3.4: Given a dictionary that can tell you whether a string is
     a valid word or not in constant time and given a string s of length n
     provide an efficient algorithm that can tell whether s can be reconstituted
     as a sequence of valid words. In the event that the string is valid, your
     algorithm should output the corresponding sequence of words.
     */
    public static boolean validWords(Set<String> wordList, String s){
        boolean foundValidWordsTill[] = new boolean[s.length()+1];
        //foundValidWordsTill[0] = true;
        for(int i = 0; i < s.length() ; i++){

            for(int j = i ; j >=0 ; j--){
                String word = s.substring(j,i+1);

                if(((j > 0 && foundValidWordsTill[j-1]) || (j==0))  && wordList.contains(word)){
                    foundValidWordsTill[i] = true;
                    break;
                }
            }
        }
        if(foundValidWordsTill[s.length()-1])
            System.out.println("String : "+ s + " has valid words");

        return foundValidWordsTill[s.length()];
    }

    /**
     * The US President is elected by the members of the Electoral College. The
     number of electors per state and Washington DC are given Table 2.
     A11 electors from each state as well as  DC cast their vote for
     the same candidate.
     Suppose there are two candidates for the presidential election.
     How will you determine if a tie is possible.
     */
    public static void tiePossibility(Integer[] numElectorsPerState){

        // build hash


        List<Integer> temp = Arrays.asList(numElectorsPerState);
        int maxNum = Collections.max(temp);


        boolean[][] differencePossibility = new boolean[numElectorsPerState.length][maxNum+1];

        for(int i = 0; i < numElectorsPerState.length ; i++){
            int numElectorsForCurrentState = numElectorsPerState[i];
            for(int j = 0; j<= maxNum ;j++){
                // differencePossibility[i][j] = possibility of ending with state i
                // with a difference in votes by value numElectors[j]
                int diff = j;

                if(i >0){

                    if(differencePossibility[i-1][j]){
                        int a = Math.abs()
                        differencePossibility[i]
                    }

                    int posToCheck = Math.abs(numElectorsForCurrentState-diff);

                    if(differencePossibility[i-1][posToCheck]){
                        differencePossibility[i][diff] = true;
                    }

                }else{
                    differencePossibility[i][numElectorsForCurrentState] = true;
                }
            }
        }

        if(differencePossibility[(numElectorsPerState.length - 1)][0]){
            System.out.println(" A Tie is Possible");
        }else{
            System.out.println(" A Tie is NOT Possible");
        }

    }

//todo : Edit Distance


}
